package pro.softzhang.algo.lc0;

import pro.softzhang.algo.common.ListNode;
import pro.softzhang.algo.common.Utils;
import pro.softzhang.algo.flag.knowledge.KDoublePointer;
import pro.softzhang.algo.flag.knowledge.KLinkedList;
import pro.softzhang.algo.flag.x.XOptimal;

/**
 * 19. 删除链表的倒数第 N 个结点
 * https://leetcode.cn/problems/remove-nth-node-from-end-of-list
 */
@KLinkedList
public class LC19_RemoveNthNodeFromEndOfList {
    public static void main(String[] args) {
        ListNode head = new ListNode(1, new ListNode(2, new ListNode(3, new ListNode(4, new ListNode(5, null)))));
        // ListNode head = new ListNode(1, null);
        int n = 2;
        Utils.printLinkedList(head);
        head = new Solution2().removeNthFromEnd(head, n);
        Utils.printLinkedList(head);
    }

    /**
     * 双指针遍历一次
     */
    @KDoublePointer
    @XOptimal
    static
    class Solution {
        public ListNode removeNthFromEnd(ListNode head, int n) {
            ListNode dummy = new ListNode(Integer.MIN_VALUE, head),
                    right = head,
                    left = dummy;

            for(int i = 0; i < n; i++) {
                right = right.next;
            }

            while (right != null) {
                right = right.next;
                left = left.next;
            }

            // 剪掉
            left.next = left.next.next;

            return dummy.next;
        }
    }

    /**
     * 遍历两次
     */
    static
    class Solution1 {
        public ListNode removeNthFromEnd(ListNode head, int n) {
            ListNode p = head, dummy = new ListNode(-1, head), q = dummy;

            // 统计数量
            int len = 0;
            while (p != null) {
                p = p.next;
                len++;
            }

            // 正向找到前个节点
            for (int i = 1; i <= len - n; i++) {
                q = q.next;
            }

            // 剪掉
            q.next = q.next.next;

            return dummy.next;
        }
    }

    static class Solution2 {
        public ListNode removeNthFromEnd(ListNode head, int n) {
            ListNode dummy = new ListNode(-1, head), rp = head, lp = dummy;
            for(int i = 1; i < n; i++) {
                rp = rp.next;
            }

            // 向前跑
            while(rp.next != null) {
                rp = rp.next;
                lp = lp.next;
            }

            lp.next = lp.next.next;
            return dummy.next;
        }
    }
}
